; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -passes=guard-widening,dce < %s | FileCheck %s

declare void @llvm.experimental.guard(i1,...)
declare i1 @dummy()

; This tests shows the incorrect behavior of guard widening in terms of
; interaction with poison values.

; Let x incoming parameter is used for rane checks.
; Test generates 5 checks. One of them (c2) is used to get the corretness
; of nuw/nsw flags for x3 and x5. Others are used in guards and represent
; the checks x + 10 u< L, x + 15 u< L, x + 20 u< L and x + 3 u< L.
; The first two checks are in the first basic block and guard widening
; considers them as profitable to combine.
; When c4 and c3 are considered, number of check becomes more than two
; and combineRangeCheck consider them as profitable even if they are in
; different basic blocks.
; Accoding to algorithm of combineRangeCheck it detects that c3 and c4
; are enough to cover c1 and c5, so it ends up with guard of c3 && c4
; while both of them are poison at entry. This is a bug.

define void @combine_range_checks(i32 %x) {
; CHECK-LABEL: @combine_range_checks(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[X_GW_FR:%.*]] = freeze i32 [[X:%.*]]
; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X_GW_FR]], 0
; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[X2]], 200
; CHECK-NEXT:    [[X3:%.*]] = add i32 [[X_GW_FR]], 3
; CHECK-NEXT:    [[C3:%.*]] = icmp ult i32 [[X3]], 100
; CHECK-NEXT:    [[X4:%.*]] = add i32 [[X_GW_FR]], 20
; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[X4]], 100
; CHECK-NEXT:    [[WIDE_CHK2:%.*]] = and i1 [[C4]], [[C3]]
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK2]]) [ "deopt"(i64 1) ]
; CHECK-NEXT:    br i1 [[C2]], label [[OK:%.*]], label [[OUT:%.*]]
; CHECK:       ok:
; CHECK-NEXT:    br label [[OUT]]
; CHECK:       out:
; CHECK-NEXT:    ret void
;
entry:
  %x1 = add i32 %x, 10
  %c1 = icmp ult i32 %x1, 100
  %x2 = add i32 %x, 0
  %c2 = icmp ult i32 %x2, 200
  %x3 = add nuw nsw i32 %x, 3
  %c3 = icmp ult i32 %x3, 100
  %x4 = add nuw nsw i32 %x, 20
  %c4 = icmp ult i32 %x4, 100
  %x5 = add i32 %x, 15
  %c5 = icmp ult i32 %x5, 100
  call void(i1, ...) @llvm.experimental.guard(i1 %c1) [ "deopt"(i64 1) ]
  call void(i1, ...) @llvm.experimental.guard(i1 %c5) [ "deopt"(i64 5) ]
  br i1 %c2, label %ok, label %out
ok:
  call void(i1, ...) @llvm.experimental.guard(i1 %c4) [ "deopt"(i64 4) ]
  call void(i1, ...) @llvm.experimental.guard(i1 %c3) [ "deopt"(i64 3) ]
  br label %out
out:
  ret void
}

; This is similar to @combine_range_checks but shows that simple freeze
; over c3 and c4 will not help due to with X = SMAX_INT, guard with c1 will
; go to deoptimization. But after guard widening freeze of c3 and c4 may return
; true due to c3 and c4 are poisons and we pass guard executing side effect store
; which never been executed in original program.
define void @combine_range_checks_with_side_effect(i32 %x, ptr %p) {
; CHECK-LABEL: @combine_range_checks_with_side_effect(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[X_GW_FR:%.*]] = freeze i32 [[X:%.*]]
; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X_GW_FR]], 0
; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[X2]], 200
; CHECK-NEXT:    [[X3:%.*]] = add i32 [[X_GW_FR]], 3
; CHECK-NEXT:    [[C3:%.*]] = icmp ult i32 [[X3]], 100
; CHECK-NEXT:    [[X4:%.*]] = add i32 [[X_GW_FR]], 20
; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[X4]], 100
; CHECK-NEXT:    [[WIDE_CHK2:%.*]] = and i1 [[C4]], [[C3]]
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK2]]) [ "deopt"(i64 1) ]
; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
; CHECK-NEXT:    br i1 [[C2]], label [[OK:%.*]], label [[OUT:%.*]]
; CHECK:       ok:
; CHECK-NEXT:    br label [[OUT]]
; CHECK:       out:
; CHECK-NEXT:    ret void
;
entry:
  %x1 = add i32 %x, 10
  %c1 = icmp ult i32 %x1, 100
  %x2 = add i32 %x, 0
  %c2 = icmp ult i32 %x2, 200
  %x3 = add nuw nsw i32 %x, 3
  %c3 = icmp ult i32 %x3, 100
  %x4 = add nuw nsw i32 %x, 20
  %c4 = icmp ult i32 %x4, 100
  %x5 = add i32 %x, 15
  %c5 = icmp ult i32 %x5, 100
  call void(i1, ...) @llvm.experimental.guard(i1 %c1) [ "deopt"(i64 1) ]
  call void(i1, ...) @llvm.experimental.guard(i1 %c5) [ "deopt"(i64 5) ]
  store i32 0, ptr %p
  br i1 %c2, label %ok, label %out
ok:
  call void(i1, ...) @llvm.experimental.guard(i1 %c4) [ "deopt"(i64 4) ]
  call void(i1, ...) @llvm.experimental.guard(i1 %c3) [ "deopt"(i64 3) ]
  br label %out
out:
  ret void
}


; The test shows the bug in guard widening. Critical pieces.
; There is a %cond_1 check which provides the correctness of nuw nsw in %b.shift.
; %b.shift and %cond_2 are poisons and after guard widening it leads to UB
; for both arithmetic and logcal and.
define void @simple_case(i32 %a, i32 %b, i1 %cnd) {
; CHECK-LABEL: @simple_case(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B_GW_FR:%.*]] = freeze i32 [[B:%.*]]
; CHECK-NEXT:    [[COND_0:%.*]] = icmp ult i32 [[A:%.*]], 10
; CHECK-NEXT:    [[B_SHIFT:%.*]] = add i32 [[B_GW_FR]], 5
; CHECK-NEXT:    [[COND_2:%.*]] = icmp ult i32 [[B_SHIFT]], 10
; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0]], [[COND_2]]
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[COND_1:%.*]] = icmp ult i32 [[B_GW_FR]], 10
; CHECK-NEXT:    br i1 [[COND_1]], label [[OK:%.*]], label [[LEAVE_LOOPEXIT:%.*]]
; CHECK:       ok:
; CHECK-NEXT:    br i1 [[CND:%.*]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
; CHECK:       leave.loopexit:
; CHECK-NEXT:    br label [[LEAVE:%.*]]
; CHECK:       leave:
; CHECK-NEXT:    ret void
;
entry:
  %cond_0 = icmp ult i32 %a, 10
  %b.shift = add nuw nsw i32 %b, 5
  %cond_2 = icmp ult i32 %b.shift, 10
  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  br label %loop

loop:
  %cond_1 = icmp ult i32 %b, 10
  br i1 %cond_1, label %ok, label %leave.loopexit
ok:
  call void (i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
  br i1 %cnd, label %loop, label %leave.loopexit

leave.loopexit:
  br label %leave

leave:
  ret void
}

declare ptr @fake_personality_function()

define void @case_with_invoke(i1 %c, i1 %gc) personality ptr @fake_personality_function {
; CHECK-LABEL: @case_with_invoke(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[C:%.*]], label [[NORMAL:%.*]], label [[INVOK:%.*]]
; CHECK:       invok:
; CHECK-NEXT:    [[INVOKE_RESULT:%.*]] = invoke i1 @dummy()
; CHECK-NEXT:    to label [[NORMAL]] unwind label [[EXCEPTION:%.*]]
; CHECK:       normal:
; CHECK-NEXT:    [[PHI_C:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[INVOKE_RESULT]], [[INVOK]] ]
; CHECK-NEXT:    [[PHI_C_GW_FR:%.*]] = freeze i1 [[PHI_C]]
; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[GC:%.*]], [[PHI_C_GW_FR]]
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
; CHECK-NEXT:    ret void
; CHECK:       exception:
; CHECK-NEXT:    [[LANDING_PAD:%.*]] = landingpad { ptr, i32 }
; CHECK-NEXT:    cleanup
; CHECK-NEXT:    ret void
;
entry:
  br i1 %c, label %normal, label %invok

invok:
  %invoke.result = invoke i1 @dummy() to label %normal unwind label %exception

normal:
  %phi.c = phi i1 [true, %entry], [%invoke.result, %invok]
  call void (i1, ...) @llvm.experimental.guard(i1 %gc) [ "deopt"() ]
  call void (i1, ...) @llvm.experimental.guard(i1 %phi.c) [ "deopt"() ]
  ret void

exception:
  %landing_pad = landingpad { ptr, i32 } cleanup
  ret void
}

define void @case_with_invoke_in_latch(i1 %c, i1 %gc) personality ptr @fake_personality_function {
; CHECK-LABEL: @case_with_invoke_in_latch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[HEADER:%.*]]
; CHECK:       header:
; CHECK-NEXT:    [[PHI_C:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[INVOKE_RESULT:%.*]], [[HEADER]] ]
; CHECK-NEXT:    [[PHI_C_GW_FR:%.*]] = freeze i1 [[PHI_C]]
; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[GC:%.*]], [[PHI_C_GW_FR]]
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
; CHECK-NEXT:    [[INVOKE_RESULT]] = invoke i1 @dummy()
; CHECK-NEXT:    to label [[HEADER]] unwind label [[EXCEPTION:%.*]]
; CHECK:       exception:
; CHECK-NEXT:    [[LANDING_PAD:%.*]] = landingpad { ptr, i32 }
; CHECK-NEXT:    cleanup
; CHECK-NEXT:    ret void
;
entry:
  br label %header

header:
  %phi.c = phi i1 [false, %entry], [%invoke.result, %header]
  call void (i1, ...) @llvm.experimental.guard(i1 %gc) [ "deopt"() ]
  call void (i1, ...) @llvm.experimental.guard(i1 %phi.c) [ "deopt"() ]
  %invoke.result = invoke i1 @dummy() to label %header unwind label %exception

exception:
  %landing_pad = landingpad { ptr, i32 } cleanup
  ret void
}

declare void @dummy_vec(<4 x i1> %arg)

define void @freeze_poison(i1 %c, i1 %g) {
; CHECK-LABEL: @freeze_poison(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DOTGW_FR:%.*]] = freeze i1 poison
; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
; CHECK:       left:
; CHECK-NEXT:    call void @dummy_vec(<4 x i1> <i1 false, i1 poison, i1 poison, i1 poison>)
; CHECK-NEXT:    ret void
; CHECK:       right:
; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[G:%.*]], [[DOTGW_FR]]
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
; CHECK-NEXT:    ret void
;
entry:
  br i1 %c, label %left, label %right

left:
  call void @dummy_vec(<4 x i1> <i1 0, i1 poison, i1 poison, i1 poison>)
  ret void


right:
  call void (i1, ...) @llvm.experimental.guard(i1 %g) [ "deopt"() ]
  call void (i1, ...) @llvm.experimental.guard(i1 poison) [ "deopt"() ]
  ret void

}

